public class Test {
    public static void main(String[] args) {
        MyComp[] a = new MyComp[100];
        for(int i=0;i<a.length;i++){
            a[i] = new MyComp(i/10, i);
        }
        
    }

    /**
         * 维护最大堆而进行的堆排序
         * @param a 要排序的数组
         * @param low 最小下表，包含
         * @param high 最大下标，不包含
         */
        static void heapSort(int[] a, int low, int high) {
            // 此处(low + high)/2正好是这个完全二叉树中叶节点的个数（从low开始）
            // 这也就相当于用约前面一半的节点把后面剩下的（全部都在叶节点）都“清洗一遍”
            // 这样非叶节点在构建过程中始终保持着堆结构，而叶节点通过”清洗“，也维持了堆结构
            // 这样，只对堆数组的0~(low + high)/2进行percolateDown就可以使整个数组维持堆结构
            for (int k = (low+high)/2; k >= low; k--) {
                // 从后往前pushDown，这样可以减少交换循环的次数
                pushDown(a, k, a[k], low, high);
            }
            
            // 将前一半pushDown下去后，头部可以确保始终最大
            // 每次取处最大的节点从后往前放
            for (;high > low;--high) {
                int max = a[low];// 此时头部必然是最大的
                pushDown(a, low, a[high], low, high-1);
                a[high] = max;
                
            }
        }

    /**
     * 堆结构中的percolateDown方法，将特定元素在队中向下压，可以看出堆是最大堆
     *
     * @param a the given array
     * @param p the start index
     * @param value the given element
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, inclusive, to be sorted
     */
        private static void pushDown(int[] a, int p, int value, int low, int high) {
            // 可以看出heap结构是从0开始的
            // 注意这种赋值方法，可以利用for循环将变量限定在代码块中
            for (int k ;; a[p] = a[p = k]) {
                // 对于从0开始下的堆结构，左右子节点的index = father<<1+1和father<<1+2;
                // 在存在偏移的时候，要先×2再减去left
                k = (p << 1) - low + 2; // 计算右子节点的index
                // 先遍历右节点是有意义的，这样可以最大限度地提高稳定性

                // 左节点也不在范围内
                if (k > high+1) {
                    break;
                }

                // 左节点在范围内但没有右节点，或者左节点比右节点要大，都把指针指向左节点
                if (k == high+1 || a[k] < a[k - 1]) {
                    --k;
                }

                // 当前指向的最大的节点也比value要小
                if (a[k] <= value) {
                    break;
                }
            }
            a[p] = value;
        }
}
class MyComp implements Comparable<MyComp> {
    int a;
    int b;

    MyComp(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(MyComp o) {
        if(a==o.a) return 0;
        else return a>o.a?1:-1;
    }

}